#include <stdio.h>

#define N 10
/**
 * File: Exercise1020.c
 * -------------------------------------------------------
 * 1.20 Modify [Program 1.3](https://gitcode.com/haoly1989/books/blob/main/AlgorithmsInC/examples/chapter1/WeightedQuickUnion.c)
 * to use the height of the trees (**longest path from any node to the root**),
 * instead of the weight, to decide whether to set `id[i] = j` or `id[j] = i`.
 * Run empirical studies to compare this variant with Program 1.3.
 * -------------------------------------------------------
 * 思路：矮树向高树合并
 * -------------------------------------------------------
 * 编译
 * gcc -o Exercise1020 Exercise1020.c
 * -----------------------------------------------------
 * 运行
 * ./Exercise1020
 * 3 4 4 9 8 0 2 3 5 6 2 9 5 9 7 3 4 8 5 6 0 2 6 1
 *
 */
int main(int argc, char **argv){
    int i, p, q, j;
    int id[N];
    int height[N];

    //初始化id数组值为索引值
    for (i = 0; i < N; i++) {
        id[i] = i;
        height[i] = 0;
    }

    // 依次处理输入对：查找+合并
    while (scanf("%d %d\n", &p, &q) == 2) {
        for (i = p; i != id[i]; i = id[i]) {
            ;
        }
        for (j = q; j != id[j]; j = id[j]) {
            ;
        }
        if (i == j) {
            continue;
        }
        //矮树向高树合并
        if (height[i] < height[j]) {
            id[i] = j;
        }else if (height[i] < height[j]){
            id[j] = i;
        }else {
            id[i] = j;
            height[j]++;
        }
        printf("%d %d\n", p, q);
    }
    return 0;
}